package Algorithm.Dp;

public class Leetcode918 {
    class Solution {
        public int maxSubarraySumCircular(int[] nums) {
            int max = nums[0];
            int cur = nums[0];
            for(int i=1;i<nums.length;i++){
                cur = Math.max(cur+nums[i], nums[i]);
                max = Math.max(cur,max);
            }

            int[] maxRight = new int[nums.length];
            int n = nums.length-1;
            maxRight[n] = nums[n];
            int sum  = nums[n];
            for(int i=n-1;i>-1;i--){
                sum = sum + nums[i];
                maxRight[i] = Math.max(maxRight[i+1],sum);

            }

            int leftSum = 0;
            for(int i=0;i<n-1;i++){
                leftSum += nums[i];
                max = Math.max(max,leftSum+maxRight[i+1]);
            }

            return max;

        }
    }
}
